<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeSet.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 *
 */
require_once( "util/AbstractSet.php" );
require_once( "util/SortedSet.php" );
require_once( "util/TreeMap.php" );
/** 
 * Class TreeSet
 *
 * This class implements the Set interface, backed by a TreeMap instance. This class guarantees that the sorted set 
 * will be in ascending element order, sorted according to the natural order  of the elements (see Comparable), or by 
 * the comparator provided at set creation time, depending on which constructor is used.
 * 
 * This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
 * 
 * Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with 
 * equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of 
 * consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a 
 * TreeSet instance performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed 
 * equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its 
 * ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.
 * 
 * Note that this implementation is not synchronized. If multiple threads access a set concurrently, and at least one of 
 * the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on 
 * some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the 
 * Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to 
 * the set:
 *      
 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
 * 
 * The CollectionIterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the 
 * iterator is created, in any way except through the iterator's own remove method, the iterator will throw a 
 * ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, 
 * rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
 * 
 * Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make 
 * any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw 
 * ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended 
 * on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
 * 
 * This class is a member of the PHP Collections Framework. 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeSet.php 14 2006-11-28 22:05:19Z rdff3 $
 */
class TreeSet extends AbstractSet implements SortedSet {
	
	private $m;
	private $keySet;
	
	private $PRESENT;
	
	private function __construct2( SortedMap $m )  {
		$this->m = $m;
		$this->keySet = $m->keySet();
		$this->PRESENT = new Object();
	}
	
	public function __construct( Comparator $c = null) {
		if (is_null($c))
			$this->__construct2( new TreeMap() );
		else
			$this->__construct2( new TreeMap( $c ) );
	}
	
	public function iterator() {
		return $this->keySet->iterator();
	}
	
	public function size() {
		return $this->m->size();
	}
	
	public function isEmpty() {
		return $this->m->isEmpty();
	}
	
	public function contains( Object $o ) {
		return $this->m->containsKey( $o );
	}
	
	public function add( Object $o ) { 
		return $this->m->put( $o, $this->PRESENT) == null;
	}
	
	public function remove( Object $o ) {
		return $this->m->remove( $o ) == $this->PRESENT;
	}
	
	public function clear() {
		$this->m->clear();
	}
	
	public function addAll( Collection $c ) {
		// Use linear time version if applicable
		if ($this->m->size() == 0 && $c->size() > 0 && $c instanceof SortedSet && $this->m instanceof TreeMap) {
			$set = $c;
			$map = $this->m;
			$cc = $set->comparator();
			$mc = $map->comparator();
			if ( $cc == $mc || ( $cc != null && $cc->equals( $mc )) ) {
				$map->addAllForTreeSet( $set, $this->PRESENT );
				return true;
			}
		
		}
		return parent::addAll( $c );
	}
	
	public function subSet( Object $fromElement, Object $toElement ) {
		return new TreeSet( $this->m->subMap( $fromElement, $toElement ) );
	}
	
	public function headSet( Object $toElement ) {
		return new TreeSet( $this->m->headMap( $toElement ));
	}
	public function tailSet( Object $fromElement ) {
		return new TreeSet( $this->m->tailMap( $fromElement ));
	}
	
	public function comparator() {
		return $this->m->comparator();
	}
	
	public function first() {
		return $this->m->firstKey();
	}
	
	public function last() {
		return $this->m->lastKey();
	}
	
}

?>